/**
 * 
 */
package com.jeearsenal.ds;

/**
 * @author monika
 */
public class BinaryTree<T extends Comparable<T>> {
	/*
	 * the root of the binary tree
	 */
	private BinaryNode root;
	
	/**
	 * @author monika
	 */
	private class BinaryNode {
		T data;
		BinaryNode left;
		BinaryNode right;
		
		public BinaryNode() {
			data = null;
			left = right = null;
		}
		
		BinaryNode(T newData){
			data = newData;
			left = right = null;
		}
	}
	
	/**
	 * to create an empty tree.
	 */
	public BinaryTree(){
		root = null;
	}
	
	/**
	 * to insert a new node in the tree.
	 * New data with the same values are inserted as the left child.
	 * 
	 * @param newData
	 */
	public void insert(T newData){
		root =  insert(root, newData);
	}
	
	/**
	 * to search a given 'value' in the tree.
	 * 
	 * @param key
	 * @return true if key exists in the tree; false otherwise.
	 */
	public boolean search(T key){
		return (search(root, key) != null)  ;
	}
	
	/**
	 * recurrsive method for insert.
	 * 
	 * @param node
	 * @param newData
	 * @return the new root.
	 */
	protected BinaryNode insert(BinaryNode node, T newData) {
		if(node == null){
			node = new BinaryNode(newData);
		}else{
			if(node.data.compareTo(newData) <= 0) {
				node.left = insert(node.left, newData);
			}else{
				node.right = insert(node.right,  newData);
			}
		}
		return node;		
	}

	/**
	 * non-recurrsive search
	 * @param node
	 * @param key
	 * @return true if 'key' found in the tree; ;false otherwise
	 */
	protected BinaryNode search(BinaryNode node, T key) {
		if(node == null){
			return null;
		}
		while(node != null){
			if(node.data.compareTo(key) == 0){
				return node;
			} else {
				if(node.data.compareTo(key) < 0){
					node = node.left;
				}else {
					node = node.right;
				}
			}
		}
		return null;
	}
	

}
